{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Make Rope Colorful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使绳子变成彩色的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 把 <code>n</code> 个气球排列在一根绳子上。给你一个下标从 <strong>0</strong> 开始的字符串 <code>colors</code> ，其中 <code>colors[i]</code> 是第 <code>i</code> 个气球的颜色。</p>\n",
    "\n",
    "<p>Alice 想要把绳子装扮成 <strong>彩色</strong> ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 <strong>彩色</strong> 。给你一个下标从 <strong>0</strong> 开始的整数数组 <code>neededTime</code> ，其中 <code>neededTime[i]</code> 是 Bob 从绳子上移除第 <code>i</code> 个气球需要的时间（以秒为单位）。</p>\n",
    "\n",
    "<p>返回 Bob 使绳子变成 <strong>彩色</strong> 需要的 <strong>最少时间</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/13/ballon1.jpg\" style=\"width: 404px; height: 243px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = \"abaac\", neededTime = [1,2,3,4,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。\n",
    "Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。\n",
    "移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/13/balloon2.jpg\" style=\"width: 244px; height: 243px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = \"abc\", neededTime = [1,2,3]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/13/balloon3.jpg\" style=\"width: 404px; height: 243px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = \"aabaa\", neededTime = [1,2,3,4,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。\n",
    "移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == colors.length == neededTime.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= neededTime[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>colors</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-make-rope-colorful](https://leetcode.cn/problems/minimum-time-to-make-rope-colorful/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-make-rope-colorful](https://leetcode.cn/problems/minimum-time-to-make-rope-colorful/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abaac\"\\n[1,2,3,4,5]', '\"abc\"\\n[1,2,3]', '\"aabaa\"\\n[1,2,3,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        cnt=0\n",
    "        for i in range(1,n):\n",
    "            if colors[i]==colors[i-1]:\n",
    "                if neededTime[i]>=neededTime[i-1]:\n",
    "                    cnt+=neededTime[i-1]\n",
    "                    neededTime[i-1]=neededTime[i]\n",
    "                else:\n",
    "                    cnt+=neededTime[i]\n",
    "                    neededTime[i] = neededTime[i-1]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        while i<n:\n",
    "            if colors[i] == colors[i-1]:\n",
    "                ans += min(neededTime[i],neededTime[i-1])\n",
    "                neededTime[i] = max(neededTime[i],neededTime[i-1])\n",
    "            i += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        i =1\n",
    "        ans =0\n",
    "\n",
    "        while i<n:\n",
    "            \n",
    "            if  colors[i]==colors[i-1]:\n",
    "                ans +=min(neededTime[i],neededTime[i-1])\n",
    "                if neededTime[i]<neededTime[i-1]:\n",
    "                    neededTime[i]=neededTime[i-1]\n",
    "            i+=1\n",
    "           \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, neededTime: List[int]) -> int:\n",
    "        ans = i = 0\n",
    "        n = len(s)\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and s[i] != s[i - 1]:\n",
    "                i += 1\n",
    "            if i < n: \n",
    "                ans += min(neededTime[i], neededTime[i - 1])\n",
    "                neededTime[i] = max(neededTime[i], neededTime[i - 1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        i=0\n",
    "        j=1\n",
    "        ans=0\n",
    "        while(i<len(s) and j<len(s)):\n",
    "            if s[i]==s[j]:\n",
    "                if cost[i]<=cost[j]:\n",
    "                    ans+=cost[i]\n",
    "                    i=j\n",
    "                    j=j+1\n",
    "                else:\n",
    "                    ans+=cost[j]\n",
    "                    j=j+1\n",
    "            else:\n",
    "                i=j\n",
    "                j=j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(neededTime)\n",
    "        dp=[inf]*(n)\n",
    "        dp[0] = 0\n",
    "        for i in range(1,n):\n",
    "            if colors[i] != colors[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = min(neededTime[i],neededTime[i-1]) + dp[i-1]\n",
    "                neededTime[i] = max(neededTime[i],neededTime[i-1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minCost(self, colors, neededTime):\n",
    "    n = len(colors)\n",
    "    ans = 0\n",
    "    \n",
    "    lt = neededTime[0]\n",
    "\n",
    "    for i in range(1, n):\n",
    "      if colors[i] == colors[i - 1]:\n",
    "        ans += min(neededTime[i], lt)\n",
    "        lt = max(lt, neededTime[i])\n",
    "      else:\n",
    "        lt = neededTime[i]\n",
    "\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(colors)\n",
    "        l,r = 0,1\n",
    "        while r<n:\n",
    "            if colors[l] != colors[r]:\n",
    "                ans += sum(neededTime[l:r])-max(neededTime[l:r])\n",
    "                l = r\n",
    "            r += 1\n",
    "        if l != n-1:\n",
    "            ans += sum(neededTime[l:r])-max(neededTime[l:r])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        i = res = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            maxv = s = neededTime[i]\n",
    "            while j < n and colors[j] == colors[j - 1]:\n",
    "                maxv = max(maxv, neededTime[j])\n",
    "                s += neededTime[j]\n",
    "                j += 1\n",
    "            res += s - maxv\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        current_color = \"\"\n",
    "        time_list = []\n",
    "        for i, color in enumerate(colors):\n",
    "            if color != current_color:\n",
    "                current_color = color\n",
    "                time_list.append(neededTime[i])\n",
    "            else:\n",
    "                if neededTime[i] > time_list[-1]:\n",
    "                    time_list.pop(-1)\n",
    "                    time_list.append(neededTime[i])\n",
    "        return sum(neededTime) - sum(time_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(colors)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            cm = neededTime[i]\n",
    "            cs = neededTime[i]\n",
    "            while j < n and colors[j] == colors[j - 1]:\n",
    "                cs += neededTime[j]\n",
    "                cm = max(cm, neededTime[j])\n",
    "                j += 1\n",
    "            res += cs - cm\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = 1\n",
    "        result = 0\n",
    "        Len = len(colors)\n",
    "        if Len == 1:\n",
    "            return 0\n",
    "        while i <= Len - 2 and j <= Len - 1:\n",
    "            if colors[i] != colors[j]:\n",
    "                i += 1\n",
    "                j = i + 1\n",
    "            else:\n",
    "                while j <= Len - 1 and colors[i] == colors[j]:\n",
    "                    j += 1\n",
    "                result += sum(neededTime[i: j]) - max(neededTime[i: j])\n",
    "                i = j\n",
    "                j = i + 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        if len(colors) < 2:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l, r = 0, 1\n",
    "\n",
    "        def cal_res(l, r):\n",
    "            return sum(neededTime[l:r]) - max(neededTime[l:r]) if r - l > 1 else 0\n",
    "\n",
    "        while r < len(colors):\n",
    "            if colors[r] == colors[l]:\n",
    "                r += 1\n",
    "            else:\n",
    "                res += cal_res(l, r)\n",
    "                l = r\n",
    "                r += 1\n",
    "\n",
    "        res += cal_res(l, r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for i in range(len(colors)-1):\n",
    "            if colors[i] == colors[i+1]:\n",
    "                ret += min(neededTime[i:i+2])\n",
    "                neededTime[i+1] = max(neededTime[i:i+2])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        i = 0\n",
    "        length = len(colors)\n",
    "        ret = 0\n",
    "\n",
    "        while i < length:\n",
    "            ch = colors[i]\n",
    "            maxValue = 0\n",
    "            total = 0\n",
    "\n",
    "            while i < length and colors[i] == ch:\n",
    "                maxValue = max(maxValue, neededTime[i])\n",
    "                total += neededTime[i]\n",
    "                i += 1\n",
    "            \n",
    "            ret += total - maxValue\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        total = sum(neededTime)\n",
    "        temp = 0\n",
    "        i = 0\n",
    "        # 有重复，需要保留最大的\n",
    "        while i < len(colors):\n",
    "            # 初始化一个字符\n",
    "            ch = colors[i]\n",
    "            max_value = 0\n",
    "            while i < len(colors):\n",
    "                if ch != colors[i]:\n",
    "                    break\n",
    "                if ch == colors[i]:\n",
    "                    max_value = max(max_value, neededTime[i])\n",
    "                i += 1\n",
    "            temp += max_value\n",
    "\n",
    "        return total - temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "                colors_list = [i for i in colors ]\n",
    "                c_len = len(colors_list)\n",
    "                time_list = 0\n",
    "                for i in range(c_len):\n",
    "                    if i +1< c_len:\n",
    "                        if colors_list[i] == colors_list[i+1]:\n",
    "                            if neededTime[i] > neededTime[i+1]:\n",
    "                                time_list += neededTime[i+1]\n",
    "                                neededTime[i+1] = neededTime[i]\n",
    "                            else:\n",
    "                                time_list+=  neededTime[i]\n",
    "                return time_list\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(neededTime)\n",
    "        last = 0\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            if colors[i] != colors[last]:\n",
    "                last = i\n",
    "            else:\n",
    "                if neededTime[i] > neededTime[last]:\n",
    "                    ans += neededTime[last]\n",
    "                    last = i\n",
    "                else:\n",
    "                    ans += neededTime[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "                colors_list = [i for i in colors ]\n",
    "                c_len = len(colors_list)\n",
    "                time_list = 0\n",
    "                for i in range(c_len):\n",
    "                    if i +1< c_len:\n",
    "                        if colors_list[i] == colors_list[i+1]:\n",
    "                            if neededTime[i] > neededTime[i+1]:\n",
    "                                time_list += neededTime[i+1]\n",
    "                                neededTime[i+1] = neededTime[i]\n",
    "                            else:\n",
    "                                time_list+=  neededTime[i]\n",
    "                return time_list\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        res, max_num, min_num = 0, cost[0], cost[0]\n",
    "        for i in range(len(s)-1): \n",
    "            min_num = min(cost[i+1], max_num)\n",
    "            max_num = max(cost[i+1], max_num)\n",
    "            if s[i] == s[i+1]: # 判断是否是重复字符\n",
    "                res += min_num  # 若是，加上较小成本    \n",
    "            else :\n",
    "                min_num, max_num = cost[i+1], cost[i+1]\n",
    "                # 不是重复字符，令min_num, max_num等于下一个字符所对应的成本\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "                colors_list = [i for i in colors ]\n",
    "                c_len = len(colors_list)\n",
    "                time_list = []\n",
    "                \n",
    "                for i in range(c_len):\n",
    "                    if i +1< c_len:\n",
    "                        if colors_list[i] == colors_list[i+1]:\n",
    "                            if neededTime[i] > neededTime[i+1]:\n",
    "                                t =  neededTime[i+1]\n",
    "                                neededTime[i+1] = neededTime[i]\n",
    "                                time_list.append(t)\n",
    "                            else:\n",
    "                                    t = neededTime[i]\n",
    "                                    time_list.append(t)\n",
    "                return sum(time_list)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        same_colors = []\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if colors[i] == colors[i - 1]:\n",
    "                if not same_colors:\n",
    "                    same_colors.append(neededTime[i - 1])\n",
    "                same_colors.append(neededTime[i])\n",
    "            elif same_colors:\n",
    "                ans += sum(same_colors) - max(same_colors)\n",
    "                same_colors = []\n",
    "            \n",
    "        return ans + sum(same_colors) - max(same_colors) if same_colors else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        curCh, curLen, curSum, curMax = s[0], 1, cost[0], cost[0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == curCh:\n",
    "                curLen += 1\n",
    "                curSum += cost[i]\n",
    "                curMax = max(curMax, cost[i])\n",
    "            else:\n",
    "                if curLen >= 2:\n",
    "                    res += (curSum - curMax)\n",
    "                curCh, curLen, curSum, curMax = s[i], 1, cost[i], cost[i]\n",
    "        if curLen >= 2:\n",
    "            res += (curSum - curMax)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        i = 0\n",
    "        length = len(colors)\n",
    "        ret = 0\n",
    "\n",
    "        while i < length:\n",
    "            ch = colors[i]\n",
    "            maxValue = 0\n",
    "            total = 0\n",
    "\n",
    "            while i < length and colors[i] == ch:\n",
    "                maxValue = max(maxValue, neededTime[i])\n",
    "                total += neededTime[i]\n",
    "                i += 1\n",
    "            \n",
    "            ret += total - maxValue\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #Loop1\n",
    "    # def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "    #     result = 0\n",
    "    #     prev = '#'\n",
    "    #     #specical workaround for last consecutive colors.\n",
    "    #     colors += '$'\n",
    "    #     neededTime.append(0)\n",
    "    #     cur_total = 0\n",
    "    #     cur_max = 0\n",
    "    #     for i, color in enumerate(colors):\n",
    "    #         if color == prev:\n",
    "    #             cur_total += neededTime[i]\n",
    "    #             cur_max = max(cur_max, neededTime[i])\n",
    "    #         else:\n",
    "    #             result += (cur_total - cur_max)\n",
    "    #             cur_total = neededTime[i]\n",
    "    #             cur_max = neededTime[i]\n",
    "    #         prev = color\n",
    "    #     return result\n",
    "    #Loop2\n",
    "    # def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "    #     n = len(colors)\n",
    "    #     i = 0\n",
    "    #     result = 0\n",
    "    #     while i < n:\n",
    "    #         prev = colors[i]\n",
    "    #         cur_total = neededTime[i]\n",
    "    #         cur_max = neededTime[i]\n",
    "    #         j = i + 1\n",
    "    #         while j < n and colors[j] == prev:\n",
    "    #             cur_total += neededTime[j]\n",
    "    #             cur_max = max(cur_max, neededTime[j])\n",
    "    #             j += 1\n",
    "    #         result += (cur_total - cur_max)\n",
    "    #         i = j\n",
    "    #     return result\n",
    "    #DP\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        result = 0\n",
    "        #dp[i]: the min cut time for colors[0:i] and last color is colors[i]\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            if i > 0 and colors[i] == colors[i-1]:\n",
    "                dp[i] = dp[i-1] + min(neededTime[i], neededTime[i-1])\n",
    "                neededTime[i] = max(neededTime[i], neededTime[i-1])\n",
    "            else:\n",
    "                dp[i] = (dp[i-1] if i > 0 else 0)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        colors += '#'\n",
    "        sm = sum(neededTime)\n",
    "        neededTime.append(10001)\n",
    "        n = len(neededTime)\n",
    "        if n == 1: return 0\n",
    "        l, remain = 0, 0\n",
    "        for r in range(1, n):\n",
    "            if colors[l] == colors[r]: continue\n",
    "            if l == r - 1:\n",
    "                remain += neededTime[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                curr = neededTime[l]\n",
    "                while l < r:\n",
    "                    curr = max(curr, neededTime[l])\n",
    "                    l += 1\n",
    "                remain += curr\n",
    "\n",
    "        return sm - remain\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(neededTime)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [0]* (n+1)\n",
    "        dp = [0]* n\n",
    "        for i in range(1,n):\n",
    "            if colors[i]!=colors[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = min(neededTime[i-1],neededTime[i])+dp[i-1]\n",
    "                if neededTime[i]>neededTime[i-1]:\n",
    "                    neededTime[i-1] = neededTime[i]\n",
    "                else:\n",
    "                    neededTime[i] = neededTime[i-1]\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        pre = colors[0]\n",
    "        now_max = neededTime[0]\n",
    "        now_index = 0\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            if colors[i] == pre:\n",
    "                if now_max < neededTime[i]:\n",
    "                    now_max = neededTime[i]\n",
    "                    now_index = i\n",
    "            else:\n",
    "                res.append(now_max)\n",
    "                pre = colors[i]\n",
    "                now_max = neededTime[i]\n",
    "                now_index = i\n",
    "        res.append(now_max)\n",
    "        return sum(neededTime) - sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        stack = []\n",
    "        total = sum(neededTime)\n",
    "\n",
    "        sum_of_max = 0 \n",
    "\n",
    "        for i,color in enumerate(colors):\n",
    "            if not stack or color!=colors[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if neededTime[i]>neededTime[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "        print(stack)\n",
    "        for index_time in stack:\n",
    "            sum_of_max+= neededTime[index_time] \n",
    "        \n",
    "        return total-sum_of_max\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        stack = []\n",
    "        total = sum(neededTime)\n",
    "\n",
    "        sum_of_max = 0 \n",
    "\n",
    "        for i,color in enumerate(colors):\n",
    "            if not stack or color!=colors[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if neededTime[i]>neededTime[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "        print(stack)\n",
    "        for index_time in stack:\n",
    "            sum_of_max+= neededTime[index_time] \n",
    "        \n",
    "        return total-sum_of_max\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        ans=0\n",
    "        i=0\n",
    "        while i<len(colors):\n",
    "            ch=colors[i]\n",
    "            maxValues=0\n",
    "            total=0\n",
    "            while i<len(colors) and colors[i]==ch:\n",
    "                maxValues=max(maxValues,neededTime[i])\n",
    "                total+=neededTime[i]\n",
    "                i+=1\n",
    "            ans+=total-maxValues\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        i = 0\n",
    "        n = len(colors)\n",
    "        tmp = []\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            tmp = []\n",
    "            tmp.append(neededTime[i])\n",
    "            r = i + 1\n",
    "            while r < n:\n",
    "                if colors[r] != colors[i]:\n",
    "                    break\n",
    "                else:\n",
    "                    tmp.append(neededTime[r])\n",
    "                r += 1\n",
    "            res += sum(tmp) - max(tmp)\n",
    "\n",
    "\n",
    "            i  = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        pre_i = 0\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            # 如果当前气球的颜色和队尾气球的颜色相同，则需要去除气球\n",
    "            if colors[i] == colors[pre_i]:\n",
    "                # 当前气球的花费比前置气球小，则去除当前气球\n",
    "                if neededTime[i] <= neededTime[pre_i]:\n",
    "                    ans += neededTime[i]\n",
    "                else:\n",
    "                    ans += neededTime[pre_i]\n",
    "                    pre_i = i\n",
    "            # 颜色不同则继续\n",
    "            else:\n",
    "                pre_i = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        t,i=0,0\n",
    "        while i<len(colors)-1:\n",
    "            if colors[i]==colors[i+1]:\n",
    "                t+=min(neededTime[i],neededTime[i+1])\n",
    "                if neededTime[i]>neededTime[i+1]:\n",
    "                    \n",
    "                else:\n",
    "                    del colors[i]\n",
    "                    del neededTime[i]\n",
    "            else:\n",
    "                i+=1\n",
    "        return t'''\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        res = 0 \n",
    "        i = 1\n",
    "        j = 0 \n",
    "        while i < len(colors) and j < len(neededTime):\n",
    "            if colors[i] == colors[i - 1]:\n",
    "                if neededTime[j] <= neededTime[i]:\n",
    "                    res += neededTime[j]\n",
    "                    j = i \n",
    "                else :\n",
    "                    res += neededTime[i]\n",
    "            else :\n",
    "                j = i \n",
    "            i += 1 \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        # 双指针进行区间计算\n",
    "        start = 0\n",
    "        end = 0\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        time = 0\n",
    "\n",
    "        while i < len(colors) - 1:\n",
    "            if colors[i] != colors[i + 1]:\n",
    "                i += 1\n",
    "                start = i\n",
    "                end = i\n",
    "            else:\n",
    "                start = i\n",
    "                end = i + 1\n",
    "                while end < len(colors) and colors[end] == colors[start]:\n",
    "                    end += 1\n",
    "                # end如果在不满足后方条件时跳出，则end会比预期+1，所以需要减1进行计算\n",
    "                end = end - 1\n",
    "                consume = neededTime[start : end + 1]\n",
    "                # 通过运算方法获取非最大值的所有其余元素的和\n",
    "                time += sum(consume) - max(consume)\n",
    "                i = end\n",
    "        \n",
    "        return time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        n = len(colors)\n",
    "        while i < n:\n",
    "            start = i\n",
    "            temp = neededTime[start]\n",
    "            i += 1\n",
    "            while i < n and colors[i] == colors[start]:\n",
    "                temp += neededTime[i]\n",
    "                i += 1\n",
    "            if temp > neededTime[start]:\n",
    "                ans += temp - max(neededTime[start:i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            start, total, max_val = i, 0, 0\n",
    "            while i < n and colors[i] == colors[start]:\n",
    "                max_val = max(neededTime[i], max_val)\n",
    "                total += neededTime[i]\n",
    "                i += 1\n",
    "            ans += total - max_val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        answer = 0 \n",
    "        colors_length = len(colors)\n",
    "        i = 0 \n",
    "        while i < colors_length:\n",
    "            max_needed_time = neededTime[i]\n",
    "            cost = neededTime[i]\n",
    "            while i + 1 < colors_length and colors[i] == colors[i + 1]:\n",
    "                cost += neededTime[i + 1]\n",
    "                max_needed_time = max(max_needed_time, neededTime[i + 1])\n",
    "                i += 1 \n",
    "            answer += (cost - max_needed_time)\n",
    "            i += 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        res = 0\n",
    "        cut = [colors[0]]\n",
    "        for index, item in enumerate(colors[1:]):\n",
    "            if item != cut[0]:\n",
    "                if len(cut) > 1:\n",
    "                    cut_time = neededTime[index + 1 - len(cut):index + 1]\n",
    "                    res += sum(cut_time) - max(cut_time)\n",
    "                cut=[item]\n",
    "            else:\n",
    "                cut.append(item)\n",
    "        if len(cut) > 1:\n",
    "            cut_time = neededTime[len(colors) - len(cut):]\n",
    "            res += sum(cut_time) - max(cut_time)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        result, i = 0, 0\n",
    "        pre = colors[0]\n",
    "\n",
    "        while i<len(colors):\n",
    "            tCost = []\n",
    "            while i<len(colors) and colors[i]==pre:\n",
    "                tCost.append(neededTime[i])\n",
    "                i += 1\n",
    "            if len(tCost)>1:\n",
    "                result += sum(tCost) - max(tCost)\n",
    "            if i==len(colors):\n",
    "                break\n",
    "            pre = colors[i]\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and colors[i] == colors[i-1]:\n",
    "                i += 1\n",
    "            if i > start + 1:\n",
    "                ans += sum(neededTime[start:i]) - max(neededTime[start:i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        i, n = 0, len(colors)\n",
    "        ans = 0\n",
    "        k = 0\n",
    "        colors = list(colors)\n",
    "        while i < n:\n",
    "            k = neededTime[i]\n",
    "            while i < n - 1 and colors[i] == colors[i + 1]:\n",
    "                ans += min(k, neededTime[i + 1])\n",
    "                k = max(k, neededTime[i + 1])\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and colors[i] == colors[i-1]:\n",
    "                i += 1\n",
    "            ans += sum(neededTime[start: i]) - max(neededTime[start: i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        pre = None\n",
    "        cnt = 0\n",
    "        times = []\n",
    "        ans = 0\n",
    "        for ch, time in zip(colors + \"?\", neededTime + [0]):\n",
    "            if ch == pre:\n",
    "                cnt += 1\n",
    "                times.append(time)\n",
    "            else:\n",
    "                if times:\n",
    "                    ans += sum(times) - max(times)\n",
    "                    times = []\n",
    "                cnt = 1\n",
    "                times.append(time)\n",
    "            pre = ch\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        dp = [0] * n\n",
    "        end_info = [colors[0],neededTime[0]]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if colors[i] == end_info[0]:\n",
    "                dp[i] = dp[i-1] + min(end_info[1],neededTime[i])\n",
    "                end_info[1] = max(end_info[1],neededTime[i])\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "                end_info[0] = colors[i]\n",
    "                end_info[1] = neededTime[i]\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        queue = []\n",
    "        for char in s:\n",
    "            if queue and queue[-1][0] == char:\n",
    "                queue[-1][1] += 1\n",
    "            else:\n",
    "                queue.append([char,1])\n",
    "        print(queue)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for char,l in queue:\n",
    "            if l > 1:\n",
    "                res += sum(sorted(cost[cur:cur+l])[:l-1])\n",
    "            cur += l \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        colors += ' '\n",
    "        tmp = [0]\n",
    "        result = 0\n",
    "        for i in range(0, len(colors) - 1):\n",
    "\n",
    "            if colors[i] == colors[i + 1]:\n",
    "\n",
    "                tmp.append(i + 1)\n",
    "            else:\n",
    "                # print(tmp)\n",
    "                # tmp 是答案\n",
    "                tmp_result = [neededTime[x] for x in tmp]\n",
    "                result += sum(tmp_result) - max(tmp_result)\n",
    "                tmp = []\n",
    "                tmp.append(i + 1)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        colors += ' '\n",
    "        tmp = [0]\n",
    "        result = 0\n",
    "        for i in range(0, len(colors)-1):\n",
    "\n",
    "            if colors[i] == colors[i + 1]:\n",
    "                # tmp.append(colors[i])\n",
    "                tmp.append(i+1)\n",
    "                # print(i)\n",
    "                # tmp.append(neededTime[i])\n",
    "            else:\n",
    "                # print(tmp)\n",
    "                # tmp 是答案\n",
    "                #if len(tmp) == 1:\n",
    "                #   continue\n",
    "                tmp_result =[neededTime[x] for x in tmp]\n",
    "                # print(tmp_result,sum(tmp_result) -max(tmp_result))\n",
    "                result += sum(tmp_result) -max(tmp_result)\n",
    "                # print(result)\n",
    "\n",
    "\n",
    "                tmp = []\n",
    "                # tmp.append(colors[i+1])\n",
    "                tmp.append(i+1)\n",
    "                # print(i)\n",
    "                # tmp.append(neededTime[i])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        if not colors:\n",
    "            return 0\n",
    "        index = 0\n",
    "        size = len(colors)\n",
    "        res = 0\n",
    "        while index < size - 1:\n",
    "            temp = [index]\n",
    "            while index < size - 1 and colors[index] == colors[index + 1]:\n",
    "                temp.append(index + 1)\n",
    "                index += 1\n",
    "            if len(temp) > 1:\n",
    "                lis = [neededTime[num] for num in temp]\n",
    "                res += sum(lis) - max(lis)\n",
    "            index += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        stk = [0]  # 存储气球的下标\n",
    "        ans = 0\n",
    "        for i in range(1, len(colors)):\n",
    "            if colors[i] == colors[stk[-1]]:\n",
    "                if neededTime[i] < neededTime[stk[-1]]:\n",
    "                    ans += neededTime[i]\n",
    "                else:\n",
    "                    ans += neededTime[stk.pop()]\n",
    "                    stk.append(i)\n",
    "            else:\n",
    "                stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        same = []\n",
    "        start = False\n",
    "        res = 0\n",
    "        for i in range(1,len(colors)):\n",
    "            if colors[i] == colors[i-1]:\n",
    "                if start == False:\n",
    "                    same.append([neededTime[i-1]])\n",
    "                    same[-1].append(neededTime[i])\n",
    "                    start = True\n",
    "                else:\n",
    "                    same[-1].append(neededTime[i])\n",
    "            else:\n",
    "                start = False\n",
    "        print(same)\n",
    "        for sam in same:\n",
    "            sam = sorted(sam)\n",
    "            res+=sum(sam[:len(sam)-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for idx, val in enumerate(s):\n",
    "            if not stack:\n",
    "                stack.append((idx, val))\n",
    "                continue\n",
    "            if val == stack[-1][1]:\n",
    "                if cost[idx]<cost[stack[-1][0]]:\n",
    "                    res += cost[idx]\n",
    "                else:\n",
    "                    res += cost[stack[-1][0]]\n",
    "                    stack.append((idx, val))\n",
    "            else:\n",
    "                stack.append((idx, val))\n",
    "        return res\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        #bound\n",
    "        if(len(cost)<2):\n",
    "            return 0\n",
    "        if(len(cost)==2):\n",
    "                return min(cost[0],cost[1])\n",
    "\n",
    "        #body\n",
    "        #find same indexs\n",
    "        Rs = []\n",
    "        iter1 = 0\n",
    "        iter2 = 1\n",
    "        while(iter1<len(cost) and iter2<len(cost)):\n",
    "            r_ = [iter1]\n",
    "            while(iter2<len(cost) and (s[iter1] == s[iter2])):\n",
    "                r_.append(iter2)\n",
    "                iter2 += 1\n",
    "            iter1 = iter2\n",
    "            iter2 +=1 \n",
    "            if(len(r_)>1):\n",
    "                Rs.append(r_)\n",
    "        #cal remove indexs\n",
    "        costs = 0\n",
    "        for R in Rs:\n",
    "            max_temp = 0\n",
    "            for ind in R:\n",
    "                costs += cost[ind]\n",
    "                if(max_temp<cost[ind]):\n",
    "                    max_temp = cost[ind]\n",
    "            costs -= max_temp\n",
    "        return costs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        arr = []\n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            if not arr:\n",
    "                arr.append(i)\n",
    "                continue\n",
    "            if colors[arr[-1]]==colors[i]:\n",
    "                if neededTime[arr[-1]]>=neededTime[i]:\n",
    "                    ans+=neededTime[i]\n",
    "                    continue\n",
    "                else:\n",
    "                    ans+=neededTime[arr.pop()]\n",
    "                    arr.append(i)\n",
    "            else:\n",
    "                arr.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * n         #dp[i]代表将前n个元素变成彩色的所需的最小花费\n",
    "        last_idx = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] != s[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "                last_idx = i           #last_idx保存相同颜色中较大的部分\n",
    "            else:\n",
    "                if cost[last_idx] < cost[i]:\n",
    "                    dp[i] = dp[i - 1] + cost[last_idx]\n",
    "                    last_idx = i\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1] + cost[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        arr = []\n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            if not arr:\n",
    "                arr.append(i)\n",
    "                continue\n",
    "            if colors[arr[-1]]==colors[i]:\n",
    "                if neededTime[arr[-1]]>=neededTime[i]:\n",
    "                    ans+=neededTime[i]\n",
    "                    continue\n",
    "                else:\n",
    "                    ans+=neededTime[arr.pop()]\n",
    "                    arr.append(i)\n",
    "            else:\n",
    "                arr.append(i)\n",
    "        print(arr)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        choose = [0]*len(colors)\n",
    "        not_choose = [0]*len(colors)\n",
    "        choose[0] = neededTime[0]\n",
    "        i=1\n",
    "        while i<len(colors):\n",
    "            if colors[i]==colors[i-1]:\n",
    "                l = i-1\n",
    "                while l>=0 and colors[i]==colors[l]:\n",
    "                    l-=1\n",
    "                r=i+1\n",
    "                while r<len(colors) and colors[i]==colors[r]:\n",
    "                    r+=1\n",
    "                curMax = max(neededTime[l+1:r])\n",
    "                cur=0\n",
    "                for z in range(l+1,r):\n",
    "                    cur+=neededTime[z]\n",
    "                cur-=curMax\n",
    "                not_choose[r-1]=not_choose[l+1]+cur\n",
    "                choose[r-1] = not_choose[l+1]+cur\n",
    "                i=r-1\n",
    "            else:\n",
    "                not_choose[i] = min(choose[i-1],not_choose[i-1])\n",
    "                choose[i] = min(not_choose[i - 1], choose[i - 1]) + neededTime[i]\n",
    "\n",
    "            i+=1\n",
    "        return min(not_choose[len(colors)-1],choose[len(colors)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        dp = [math.inf] * (len(colors))\n",
    "        dp[0] = 0\n",
    "\n",
    "        preColor = colors[0]\n",
    "        preBallIndex = 0\n",
    "        for i in range(1, len(colors)):\n",
    "            if colors[i] == preColor:\n",
    "                dp[i] = dp[i - 1] + min(neededTime[preBallIndex], neededTime[i])\n",
    "\n",
    "                if neededTime[i] > neededTime[preBallIndex]:\n",
    "                    preBallIndex = i\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i - 1]\n",
    "                preBallIndex = i \n",
    "                preColor = colors[i]\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        problems = []\n",
    "        N = len(colors)\n",
    "        assert N == len(neededTime), 'err1'\n",
    "        last = colors[0]\n",
    "        tmp = []\n",
    "        i = 1\n",
    "        while i < N:\n",
    "            c = colors[i]\n",
    "            if c == last:\n",
    "                if not tmp:\n",
    "                    tmp = [i-1]\n",
    "                tmp.append(i)\n",
    "            else:\n",
    "                if tmp:\n",
    "                    problems.append(tmp)\n",
    "                    tmp = []\n",
    "            i += 1\n",
    "            last = c\n",
    "        if tmp:\n",
    "            problems.append(tmp)\n",
    "        # print(problems)\n",
    "        costs = 0\n",
    "        for p in problems:\n",
    "            times = neededTime[p[0]:p[-1]+1]\n",
    "            # print(times)\n",
    "            costs += sum(times) - max(times)\n",
    "        return costs\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        # 动态规划 \n",
    "        # 1.事件发展的主进程？\n",
    "        #   前n个字母的最小删除成本\n",
    "        # 2.定义状态\n",
    "        #   dp[n]表示前n个字母以第n个字母相同字母结尾的最小删除成本\n",
    "        # 3.状态转移方程\n",
    "        #   dp[n] = dp[n-1] + cost[cost_end_index] #剔除当前维护的前n-1个字符中的\"末尾字符\"\n",
    "        #   dp[n] = dp[n-1] + cost[n] #剔除第n个字符\n",
    "        #   dp[n] = dp[n-1] #不是相同字符不做处理\n",
    "        #   与最后一个字母相同的字母是必要的，那么返回的结果就是dp[-1]\n",
    "        l = len(s)\n",
    "        process = list(s)\n",
    "        dp = [0] * l\n",
    "        cost_end_index = 0\n",
    "        for n in range(1, l):\n",
    "            # 如果与结尾字母相同\n",
    "            if s[n] == s[n-1]:\n",
    "                # 从去除上个末尾元素和去除第n个字符中抉择，选取最优删除成本\n",
    "                if cost[cost_end_index]<cost[n]: \n",
    "                    dp[n] = dp[n-1] + cost[cost_end_index]\n",
    "                    process[cost_end_index] = -1\n",
    "                    cost_end_index = n\n",
    "                else:\n",
    "                    dp[n] = dp[n-1] + cost[n]\n",
    "                    process[n] = -1\n",
    "            else:\n",
    "                dp[n] = dp[n-1]\n",
    "                cost_end_index = n\n",
    "        print(process)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        # 动态规划 \n",
    "        # 1.事件发展的主进程？\n",
    "        #   前n个字母的最小删除成本\n",
    "        # 2.定义状态\n",
    "        #   dp[n]表示前n个字母以第n个字母相同字母结尾的最小删除成本\n",
    "        # 3.状态转移方程\n",
    "        #   dp[n] = dp[n-1] + cost[cost_end_index] #剔除当前维护的前n-1个字符中的\"末尾字符\"\n",
    "        #   dp[n] = dp[n-1] + cost[n] #剔除第n个字符\n",
    "        #   dp[n] = dp[n-1] #不是相同字符不做处理\n",
    "        #   与最后一个字母相同的字母是必要的，那么返回的结果就是dp[-1]\n",
    "        l = len(s)\n",
    "        process = list(s)\n",
    "        dp = [0] * l\n",
    "        cost_end_index = 0\n",
    "        for n in range(1, l):\n",
    "            # 如果与结尾字母相同\n",
    "            if s[n] == s[n-1]:\n",
    "                # 从去除上个末尾元素和去除第n个字符中抉择，选取最优删除成本\n",
    "                if cost[cost_end_index]<cost[n]: \n",
    "                    dp[n] = dp[n-1] + cost[cost_end_index]\n",
    "                    process[cost_end_index] = -1\n",
    "                    cost_end_index = n\n",
    "                else:\n",
    "                    dp[n] = dp[n-1] + cost[n]\n",
    "                    process[n] = -1\n",
    "            else:\n",
    "                dp[n] = dp[n-1]\n",
    "                cost_end_index = n\n",
    "        print(process)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: str, cost: List[int]) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        m = []\n",
    "        z = list(zip(s,cost))\n",
    "        ma = z[0][1]\n",
    "        for i in range(1,len(z)):\n",
    "            if z[i-1][0] == z[i][0]:\n",
    "                ma = max(ma,z[i][1])\n",
    "            else:\n",
    "                m.append(ma)\n",
    "                ma = z[i][1]\n",
    "        m.append(ma)\n",
    "        return sum(cost)-sum(m)\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        n = len(neededTime)\n",
    "        dp = [0] * (n+1) \n",
    "        same_color_cnt = 1                  # colors[i]往前数，与colors[i]同颜色的气球个数\n",
    "        same_color_time = neededTime[0]     # colors[i]往前数，与colors[i]同颜色的气球移除总时间\n",
    "        max_same_color_time = neededTime[0] # colors[i]往前数，与colors[i]同颜色的气球的最大移除时间\n",
    "        for i in range(1, n):\n",
    "            if colors[i] != colors[i-1]:\n",
    "                same_color_cnt = 1\n",
    "                same_color_time = neededTime[i]\n",
    "                max_same_color_time = neededTime[i]\n",
    "                dp[i+1] = dp[i]\n",
    "            else:\n",
    "                same_color_cnt += 1\n",
    "                same_color_time += neededTime[i]\n",
    "                max_same_color_time = max(max_same_color_time, neededTime[i])\n",
    "                dp[i+1] = dp[i+1-same_color_cnt] + same_color_time - max_same_color_time # 连续same_color_cnt个气球，需要移除其中时间较小的same_color_cnt-1个\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        pre=\"A\"\n",
    "        ans=[]\n",
    "        for c,time in zip(colors,neededTime):\n",
    "            if c!=pre:\n",
    "                ans.append([time])\n",
    "            else:\n",
    "                ans[-1].append(time)\n",
    "            pre=c\n",
    "        res=0\n",
    "        for row in ans:\n",
    "            if len(row)>1:\n",
    "                res+=sum(row)-max(row)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        group=[]        # 设立group\n",
    "        pre=\"A\"         # 设定pre\n",
    "        for c,time in zip(colors,neededTime):   # 遍历列表\n",
    "            if c!=pre:                  # 起点\n",
    "                group.append([time])    # 新建分组\n",
    "            else:                       # 同类\n",
    "                group[-1].append(time)  # 尾增\n",
    "            pre=c   # 更新pre\n",
    "        ans=0\n",
    "        for row in group:   # 遍历group\n",
    "            if len(row)>1:  # 如果大于1，说明需要移除 len(row)-1个\n",
    "                ans += sum(row)-max(row)      # 贪心，留下最大时间的那个，剩下都移除\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, colors: str, neededTime: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(colors)\n",
    "        res=[]\n",
    "        nums=[neededTime[0]]\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if colors[i]==colors[i-1]:\n",
    "                nums.append(neededTime[i])\n",
    "            else:\n",
    "                res.append(nums)\n",
    "                nums=[neededTime[i]]\n",
    "\n",
    "        res.append(nums)\n",
    "        for r in res:\n",
    "            if len(r)<2:\n",
    "                continue\n",
    "            else:\n",
    "                ans+=sum(r)-max(r)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
